import random

def set_insert_list(lst):
    def inner_insert(start,step):
        nonlocal lst
        for l in range(start+step,len(lst),step):
            ins = lst[l]
            i = l
            while i>=step and lst[i-step]>ins:
                lst[i]=lst[i-step]
                i-=step
            lst[i]=ins
        return lst
    return inner_insert

def shell(lst):
    insert = set_insert_list(lst)
    step = len(lst)//2
    while step>=1:
        for start in range(step):
            insert(start,step)
        step=step//2
    return insert(len(lst),1)


if __name__ == "__main__":
    n = 1000
    lst = list({random.randrange(n,10*n-1) for _ in range(n)})
    print(shell(lst)==sorted(lst))
    # print(shell(lst))